/*
 * @lc app=leetcode.cn id=133 lang=typescript
 *
 * [133] 克隆图
 */

// @lc code=start

interface INodeInfo {
  val: number;
  neighbors: number[];
}

function cloneGraph(node: _Node | null): _Node | null {
  // bfs
  // queue
  const queue = [node];
  // map record val->val
  const map = new Map<number, Set<number>>();
  const finder = new Set<number>();
  while (queue.length > 0) {
    const node = queue.pop();
    if (!node) continue;
    if (finder.has(node.val)) continue;
    finder.add(node.val);
    for (const _nb of node.neighbors) {
      if (finder.has(_nb.val)) continue;
      queue.push(_nb);
      map.set(node.val, (map.get(node.val) || new Set()).add(_nb.val));
    }
  }
  // rebuild
  const nodes: _Node[] = [];
  for (let i = 0; i < finder.size; i++) {
    nodes.push(new _Node(i + 1));
  }
  for (const [key, set] of map) {
    const node = nodes[key - 1];
    for (const val of set) {
      node.neighbors.push(nodes[val - 1]);
    }
  }
  if (nodes.length > 0) return nodes[0];
  return null;
}
// @lc code=end
